{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reduction Operations to Make the Array Elements Equal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reductionOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组元素相等的减少操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，你的目标是令 <code>nums</code> 中的所有元素相等。完成一次减少操作需要遵照下面的几个步骤：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>找出 <code>nums</code> 中的 <strong>最大</strong> 值。记这个值为 <code>largest</code> 并取其下标 <code>i</code> （<strong>下标从 0 开始计数</strong>）。如果有多个元素都是最大值，则取最小的 <code>i</code> 。</li>\n",
    "\t<li>找出 <code>nums</code> 中的 <strong>下一个最大</strong> 值，这个值 <strong>严格小于</strong> <code>largest</code> ，记为 <code>nextLargest</code> 。</li>\n",
    "\t<li>将 <code>nums[i]</code> 减少到 <code>nextLargest</code> 。</li>\n",
    "</ol>\n",
    "\n",
    "<p>返回使<em> </em><code>nums</code><em> </em>中的所有元素相等的操作次数。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,1,3]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>需要 3 次操作使 nums 中的所有元素相等：\n",
    "1. largest = 5 下标为 0 。nextLargest = 3 。将 nums[0] 减少到 3 。nums = [<strong>3</strong>,1,3] 。\n",
    "2. largest = 3 下标为 0 。nextLargest = 1 。将 nums[0] 减少到 1 。nums = [<strong>1</strong>,1,3] 。\n",
    "3. largest = 3 下标为 2 。nextLargest = 1 。将 nums[2] 减少到 1 。nums = [<strong>1</strong>,1,<strong>1</strong>] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,1]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>nums 中的所有元素已经是相等的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,2,2,3]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>需要 4 次操作使 nums 中的所有元素相等：\n",
    "1. largest = 3 下标为 4 。nextLargest = 2 。将 nums[4] 减少到 2 。nums = [1,1,2,2,<strong>2</strong>] 。\n",
    "2. largest = 2 下标为 2 。nextLargest = 1 。将 nums[2] 减少到 1 。nums = [1,1,<strong>1</strong>,2,2] 。 \n",
    "3. largest = 2 下标为 3 。nextLargest = 1 。将 nums[3] 减少到 1 。nums = [1,1,1,<strong>1</strong>,2] 。 \n",
    "4. largest = 2 下标为 4 。nextLargest = 1 。将 nums[4] 减少到 1 。nums = [1,1,1,1,<strong>1</strong>] 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 <= nums[i] <= 5 * 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reduction-operations-to-make-the-array-elements-equal](https://leetcode.cn/problems/reduction-operations-to-make-the-array-elements-equal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reduction-operations-to-make-the-array-elements-equal](https://leetcode.cn/problems/reduction-operations-to-make-the-array-elements-equal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,1,3]', '[1,1,1]', '[1,1,2,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        curr = nums[0]\n",
    "        add = 0\n",
    "        for num in nums:\n",
    "            if num != curr:\n",
    "                add+=1\n",
    "                curr= num\n",
    "            res+=add\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = size = 0\n",
    "        for x, y in pairwise(nums):\n",
    "            if x != y:\n",
    "                size += 1\n",
    "            ans += size\n",
    "        return ans\n",
    "            \n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        small = 0\n",
    "        i = j = 0\n",
    "        while i < n:\n",
    "            while j < n and nums[j] == nums[i]:\n",
    "                ans += small\n",
    "                j += 1\n",
    "            small += 1\n",
    "            i = j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        res = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i - 1] != nums[i]:\n",
    "                res += i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        acc = 0\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            if nums[i-1] != nums[i]:\n",
    "                acc += 1\n",
    "            res += acc\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0   # 总操作次数\n",
    "        cnt = 0   # 每个元素操作次数\n",
    "        for i in range(1, n):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                cnt += 1\n",
    "            res += cnt\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        return sum(n - i for i in range(1, n) if nums[i] != nums[i - 1]) if (nums := sorted(nums)) and (n := len(nums)) else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        cnt = 1\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i+1] > nums[i]:\n",
    "                res += cnt\n",
    "                cnt += 1\n",
    "            elif cnt-1:\n",
    "                res += cnt - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0   # 总操作次数\n",
    "        cnt = 0   # 每个元素操作次数\n",
    "        for i in range(1, n):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                cnt += 1\n",
    "            res += cnt\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        stack = []\n",
    "        level = 0\n",
    "        res = 0\n",
    "        \n",
    "        nums = sorted(nums)\n",
    "        for num in nums:\n",
    "            if stack and num > stack[-1]:\n",
    "                while stack and num>stack[-1]:\n",
    "                    stack.pop()\n",
    "                    res += level\n",
    "                level += 1\n",
    "            stack.append(num)\n",
    "        res += len(stack)*level\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        cnt = 1\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i+1] > nums[i]:\n",
    "                res += cnt\n",
    "                cnt += 1\n",
    "            elif (cnt-1>0):\n",
    "                res += cnt - 1\n",
    "        return res\n",
    "\n",
    "        # 1 3 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        o = nums[0]\n",
    "        n = len(nums)\n",
    "        ans = i = c = 0\n",
    "        while i < n:\n",
    "            if nums[i] == o:\n",
    "                ans += c\n",
    "            else:\n",
    "                c+=1\n",
    "                ans += c\n",
    "                o = nums[i]\n",
    "            i += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0   # 总操作次数\n",
    "        cnt = 0   # 每个元素操作次数\n",
    "        for i in range(1, n):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                cnt += 1\n",
    "            res += cnt\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n = sorted(nums)\n",
    "        cur = n[0]\n",
    "        rank = 0\n",
    "        ans = 0\n",
    "        for i, c in enumerate(n):\n",
    "            if c != cur:\n",
    "                cur = c\n",
    "                rank += 1\n",
    "            ans += rank\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(len(nums)-2, -1, -1) :\n",
    "            if nums[i] != nums[i+1] :\n",
    "                ans += len(nums)-i-1\n",
    "\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        pre, n_pre = -1, 0\n",
    "        ans = 0\n",
    "        for num in sorted(nums, reverse=True):\n",
    "            if num == pre:\n",
    "                n_pre += 1\n",
    "            else:\n",
    "                ans += n_pre\n",
    "                n_pre += 1\n",
    "                pre = num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        cnt = 0\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                cnt += 1\n",
    "            \n",
    "            res += cnt\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        N = len(nums)\n",
    "        operations = 0\n",
    "        cnt = 0\n",
    "        for idx in range(1, N):\n",
    "            if nums[idx] != nums[idx - 1]:\n",
    "                cnt += 1\n",
    "            operations += cnt\n",
    "        return operations\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()  # Step 1: Sort the nums array.\n",
    "        operations = 0\n",
    "        total_ops = 0\n",
    "        \n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] != nums[i-1]:  # Check if current element is different from previous one\n",
    "                operations += 1\n",
    "            total_ops += operations  # Add the operations needed for this step\n",
    "        \n",
    "        return total_ops\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n-1, 0, -1):\n",
    "            if nums[i] > nums[i-1]:\n",
    "                res += (n-i)\n",
    "            else:\n",
    "                continue\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        last = nums[0]\n",
    "        ans = 0\n",
    "        size = 0\n",
    "        for x, y in pairwise(nums):\n",
    "            if x != y:\n",
    "                size += 1\n",
    "            ans += size\n",
    "        return ans\n",
    "            \n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0   # 总操作次数\n",
    "        cnt = 0   # 每个元素操作次数\n",
    "        for i in range(1, n):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                cnt += 1\n",
    "            res += cnt\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        N = len(nums)\n",
    "        operations = 0 # 总操作数\n",
    "        order = 0 # 当前元素的排序值\n",
    "        for idx in range(1, N):\n",
    "            if nums[idx] != nums[idx - 1]:\n",
    "                order += 1\n",
    "            operations += order\n",
    "        return operations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        cnt = 1\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i+1] > nums[i]:\n",
    "                res += cnt\n",
    "                cnt += 1\n",
    "            elif cnt-1:\n",
    "                res += cnt - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        dp=[0]*n\n",
    "        for i in range(1,n):\n",
    "            if nums[i]==nums[i-1]:\n",
    "                dp[i]=dp[i-1]\n",
    "            elif nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            else:\n",
    "                for j in range(i-1,-1,-1):\n",
    "                    if nums[j]==nums[i]:\n",
    "                        dp[i]=dp[j]\n",
    "                    elif nums[j]<nums[i]:\n",
    "                        dp[i]=dp[j]+1\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        cnt = 0\n",
    "        for i in range(1,n):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                cnt += 1\n",
    "            res += cnt\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        index = n if nums[0] == nums[-1] else bisect.bisect_right(nums, nums[0])\n",
    "        ans, cnt = 0, 0\n",
    "        index_num = nums[-1]\n",
    "        for i in range(n - 1, index - 1, -1):\n",
    "            if nums[i] != index_num:\n",
    "                index_num = nums[i]\n",
    "                ans += cnt\n",
    "            cnt += 1\n",
    "        ans += cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        count = 0\n",
    "        numsSize = len(nums)\n",
    "        for i in range(1, numsSize):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                count += 1\n",
    "            retVal += count\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0   # 总操作次数\n",
    "        cnt = 0   # 每个元素操作次数\n",
    "        for i in range(1, n):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                cnt += 1\n",
    "            res += cnt\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res, cnt = 0, 0\n",
    "        for i in range(1, n):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                cnt += 1\n",
    "            res += cnt\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        total = presum = 0\n",
    "        for i in range(1, n):\n",
    "            if nums[i] != nums[i - 1]:\n",
    "                presum += 1\n",
    "            total += presum\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict \n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        N = len(nums)\n",
    "        operations = 0\n",
    "        cnt = 0\n",
    "        for idx in range(1, N):\n",
    "            if nums[idx] != nums[idx - 1]:\n",
    "                cnt += 1\n",
    "            operations += cnt\n",
    "        return operations\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        lst = []\n",
    "        pre = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i > 0 and nums[i] != nums[i-1]:\n",
    "                lst.append(i - pre)\n",
    "                pre = i\n",
    "        lst.append(len(nums) - pre)\n",
    "        ans = 0\n",
    "        for i, k in enumerate(lst):\n",
    "            ans += k*(len(lst)-1-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans=0\n",
    "        pivot=nums[0]\n",
    "        level=0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]>pivot:\n",
    "                level+=1\n",
    "                pivot=nums[i]\n",
    "            ans+=level\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        ##sort  connter 就像台阶\n",
    "        nums = sorted(nums)\n",
    "        o = nums[0]\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        i = c = 0\n",
    "        while i < n-1:\n",
    "            i += 1\n",
    "            if nums[i] == o:\n",
    "                ans += c\n",
    "                # pass\n",
    "            else:\n",
    "                c+=1\n",
    "                o = nums[i]\n",
    "                ans += c\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        dp=[0]*n\n",
    "        for i in range(1,n):\n",
    "            if nums[i]==nums[i-1]:\n",
    "                dp[i]=dp[i-1]\n",
    "            elif nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            \n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        Key = list(cnt.keys())\n",
    "        Key.sort()\n",
    "        ans = 0\n",
    "        n = len(Key) - 1\n",
    "        for x in Key[:0:-1]:\n",
    "            ans += cnt[x] * n\n",
    "            n -= 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        set_dict = {}\n",
    "        for tmp in nums:\n",
    "            if tmp not in set_dict:\n",
    "                set_dict[tmp] = 1\n",
    "            else:\n",
    "                set_dict[tmp] += 1\n",
    "        \n",
    "        order_list = sorted(set_dict.keys(), reverse=1)\n",
    "        #print(order_list)\n",
    "        m = len(order_list)\n",
    "        total = 0\n",
    "        for ki, key in enumerate(order_list):\n",
    "            total += set_dict[key] * (m - ki - 1)\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        c = Counter(nums)\n",
    "        ans = 0\n",
    "        for i,v in enumerate(sorted(c.keys())):\n",
    "            ans += c[v] * i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        Key = list(cnt.keys())\n",
    "        Key.sort()\n",
    "        ans = 0\n",
    "        n = len(Key) - 1\n",
    "        for x in range(n, 0, -1):\n",
    "            ans += cnt[Key[x]] * n\n",
    "            n -= 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        c = Counter(nums)\n",
    "        ans = 0\n",
    "        for i, n in enumerate(sorted(c)):\n",
    "            ans += i * c[n]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        cnt = Counter(nums)\n",
    "        dis = 1\n",
    "        mi = min(nums)\n",
    "        for k, v in cnt.items():\n",
    "            if k == mi:\n",
    "                continue\n",
    "            ans += dis * v\n",
    "            dis += 1\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        set_dict = {}\n",
    "        for tmp in nums:\n",
    "            if tmp not in set_dict:\n",
    "                set_dict[tmp] = 1\n",
    "            else:\n",
    "                set_dict[tmp] += 1\n",
    "        \n",
    "        order_list = sorted(set_dict.keys(), reverse=1)\n",
    "        #print(order_list)\n",
    "        m = len(order_list)\n",
    "        total = 0\n",
    "        for ki, key in enumerate(order_list):\n",
    "            total += set_dict[key] * (m - ki - 1)\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        c = Counter(nums)\n",
    "        ans = 0\n",
    "        for i, n in enumerate(sorted(c)[1:], 1):\n",
    "            ans += i * c[n]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        map_ = collections.Counter(nums)\n",
    "        key_list = list(sorted(map_.keys(), reverse=True))\n",
    "        count = 0\n",
    "        for i in range(len(key_list)):\n",
    "            count += map_[key_list[i]] * (len(key_list) - 1 - i)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        record = collections.defaultdict(int)\n",
    "        for i, num in enumerate(nums):\n",
    "            record[num] += 1\n",
    "        # print(record)\n",
    "        temp = sorted(record.keys(), reverse = True)\n",
    "        count = 0\n",
    "        for i in range(len(temp)-1):\n",
    "            count += record[temp[i]]\n",
    "            record[temp[i+1]] += record[temp[i]]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\r\n",
    "        c = Counter(nums)\r\n",
    "        if len(c) == 1:\r\n",
    "            return 0\r\n",
    "        nums = sorted(c.keys(), reverse=True)\r\n",
    "        ans = 0\r\n",
    "        pre = 0\r\n",
    "        for i in range(len(nums) - 1):\r\n",
    "            ans += c[nums[i]] + pre\r\n",
    "            pre += c[nums[i]]\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        s = {}\n",
    "        for n in nums:\n",
    "            if n not in s:\n",
    "                s[n] = 0\n",
    "            s[n] += 1\n",
    "        l = list(s.keys())\n",
    "        l.sort(reverse=True)\n",
    "        res = 0\n",
    "        for i in range(len(l)-1):\n",
    "            res += s[l[i]]\n",
    "            s[l[i+1]] += s[l[i]]\n",
    "            del s[l[i]]\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        c = Counter(nums)\n",
    "        ans = cnt = 0\n",
    "        for k in sorted(c, reverse=True):\n",
    "            cnt += c[k]\n",
    "            ans += cnt\n",
    "        return ans - cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        mapping = {}\n",
    "        for num in nums:\n",
    "            if(num not in mapping):\n",
    "                mapping[num] = 1\n",
    "            else:\n",
    "                mapping[num] += 1\n",
    "        arrs = sorted(mapping.keys())\n",
    "        n = len(arrs)\n",
    "        if(n == 1):\n",
    "            return 0\n",
    "        pre = 0\n",
    "        result = 0\n",
    "        for i in range(n-1,0,-1):\n",
    "            pre += mapping[arrs[i]]\n",
    "            result += pre\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        mapping = {}\n",
    "        for num in nums:\n",
    "            if(num not in mapping):\n",
    "                mapping[num] = 1\n",
    "            else:\n",
    "                mapping[num] += 1\n",
    "        arrs = sorted(mapping.keys())\n",
    "        n = len(arrs)\n",
    "        if(n == 1):\n",
    "            return 0\n",
    "        pre = 0\n",
    "        result = 0\n",
    "        for i in range(n-1,0,-1):\n",
    "            pre += mapping[arrs[i]]\n",
    "            result += pre\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        cn = Counter(nums)\n",
    "        s, ans = 0, 0\n",
    "        for k in sorted(cn, reverse=True):\n",
    "            v = cn[k]\n",
    "            ans += s\n",
    "            s += v\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        cnter = Counter(nums)\n",
    "        arr = sorted(cnter.keys())\n",
    "        return sum(i * cnter[v] for i, v in enumerate(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        nums_dict = {}\n",
    "        for num in nums:\n",
    "            if num in nums_dict:\n",
    "                nums_dict[num] += 1\n",
    "            else:\n",
    "                nums_dict[num] = 1\n",
    "        res = 0\n",
    "        for order, num in enumerate(nums_dict):\n",
    "            res += nums_dict[num] * order\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\r\n",
    "        c = Counter(nums)\r\n",
    "        if len(c) == 1:\r\n",
    "            return 0\r\n",
    "        nums = sorted(c.keys(), reverse=True)\r\n",
    "        ans = 0\r\n",
    "        pre = 0\r\n",
    "        for i in range(len(nums) - 1):\r\n",
    "            print(nums[i], c[nums[i]], pre)\r\n",
    "            ans += c[nums[i]] + pre\r\n",
    "            pre += c[nums[i]]\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        sorted_arr = sorted(set(nums))\n",
    "        idx_dict = {}\n",
    "        for i in range(1, len(sorted_arr)):\n",
    "            idx_dict[sorted_arr[i]] = i\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            if num in idx_dict:\n",
    "                cnt += idx_dict[num]\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        c = Counter(nums)\n",
    "        ans = 0\n",
    "        ks = sorted(c.keys(), reverse=True)\n",
    "        # print(ks)\n",
    "        m = len(ks)\n",
    "        for i in range(m-1):\n",
    "            ans += (m-i-1) * c[ks[i]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        a = list(set(nums))\n",
    "        a.sort()\n",
    "        d = dict()\n",
    "        for i in range(len(a)):\n",
    "            d[a[i]] = i\n",
    "        ret = 0\n",
    "        for x in nums:\n",
    "            ret += d[x]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        s = sorted(set(nums), reverse=True)\n",
    "        cnt = Counter(nums)\n",
    "        ans = 0\n",
    "\n",
    "        s.pop()\n",
    "        n = len(s)\n",
    "        for i, num in enumerate(s):\n",
    "            ans += (n - i) * cnt[num]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        s = list(set(nums))\n",
    "        s.sort()\n",
    "        dt = dict()\n",
    "        dt.update(zip(s, range(len(s))))\n",
    "\n",
    "        return sum([dt[x] for x in nums])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\r\n",
    "        cnt = Counter(nums)\r\n",
    "        # 統計比自己小的數字有幾種\r\n",
    "        keys = sorted(cnt.keys())\r\n",
    "        pre = []\r\n",
    "        for key in keys:\r\n",
    "            pre.append((pre[-1]+1 if pre else 0))\r\n",
    "        ans = 0\r\n",
    "        for i, k in enumerate(keys):\r\n",
    "            ans += cnt[k] * pre[i]\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        unique_nums = list(set(nums))\n",
    "        list.sort(unique_nums)\n",
    "        m = defaultdict(int)\n",
    "        for i in range(len(unique_nums)):\n",
    "            m[unique_nums[i]] = i\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            res += m[nums[i]]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        s = list(set(nums))\n",
    "        s.sort()\n",
    "        dt = dict()\n",
    "        dt.update(zip(s, range(len(s))))\n",
    "\n",
    "        return sum([dt[x] for x in nums])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        num_dic = collections.Counter(nums)\n",
    "        ret = 0\n",
    "        temp = 0\n",
    "        lst = list(num_dic.keys())\n",
    "        lst.sort()\n",
    "        steps = len(lst) - 1\n",
    "        while steps > 0:\n",
    "            temp += num_dic[lst.pop()]\n",
    "            ret += temp\n",
    "            steps -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        nums.sort()\n",
    "        record = Counter(nums)\n",
    "        record = sorted(record.items())\n",
    "        recordSize = len(record)\n",
    "        for i in range(1, recordSize):\n",
    "            retVal += (i * record[i][1])\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        ans = 0\n",
    "        L = sorted(set(nums))\n",
    "        for i, j in enumerate(L):\n",
    "            ans += i * cnt[j]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter()\n",
    "        for x in nums:\n",
    "            cnt[x] += 1\n",
    "        l = sorted(list(set(nums)))\n",
    "        ans = 0\n",
    "        for i in range(len(l)-1, 0, -1):\n",
    "            ans += cnt[l[i]]\n",
    "            cnt[l[i-1]] += cnt[l[i]]\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        ans = 0\n",
    "        s = 1\n",
    "        for i in range(1,len(nums)):\n",
    "            ans += cnt[nums[i]]*s\n",
    "            s += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        counter, min_num = {}, 10 ** 9\n",
    "        for num in nums:\n",
    "            counter[num] = counter.get(num, 0) + 1\n",
    "            min_num = min(min_num, num)\n",
    "        res, last_cnt = 0, 0\n",
    "        for num, cnt in sorted(counter.items(), reverse=True):\n",
    "            if num == min_num:\n",
    "                break\n",
    "            res += last_cnt + cnt\n",
    "            last_cnt += cnt\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        count = Counter(nums)\n",
    "        # print(count)\n",
    "        newnums = list(count.items())\n",
    "        newnums.sort(reverse = True)\n",
    "        n = len(newnums)\n",
    "        pre = [0]*n\n",
    "        for i in range(1,n):\n",
    "            pre[i] = pre[i-1] + newnums[i-1][1]\n",
    "        return sum(pre)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        ans = sorted(Counter(nums).items(),key= lambda x:x[0],reverse= True)\n",
    "        n = len(ans)\n",
    "        count = 0\n",
    "        i = 1\n",
    "        for x,y in ans:\n",
    "            count += y * (n - i)\n",
    "            i += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        ans = sorted(Counter(nums).items(),key= lambda x:x[0],reverse= True)\n",
    "        n = len(ans)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        count = 0\n",
    "        i = 1\n",
    "        for x,y in ans:\n",
    "            count += y * (n - i)\n",
    "            i += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        ans = 0\n",
    "        pre = 0\n",
    "        mn = min(nums)\n",
    "        for k, v in sorted(cnt.items(), reverse=True):\n",
    "            if k == mn:\n",
    "                return ans\n",
    "            ans += v + pre\n",
    "            pre += v\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict \n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        lookup = defaultdict(lambda: 0)\n",
    "        for num in nums:\n",
    "            lookup[num] += 1\n",
    "\n",
    "        ans = 0\n",
    "        left_num_cnt = 0\n",
    "        for item in sorted(lookup.items(), key= lambda item: -item[0])[:-1]:\n",
    "            ans = ans + item[1] + left_num_cnt\n",
    "            left_num_cnt += item[1]\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        cnt = sorted(Counter(nums).items(), key=lambda x: x[0], reverse=True)\n",
    "        return sum(accumulate([v for k, v in cnt[:-1]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reductionOperations(self, nums: List[int]) -> int:\n",
    "        num_dict = {}\n",
    "        for each in nums:\n",
    "            num_dict[each] = num_dict.get(each, 0) + 1\n",
    "        num_times = sorted(num_dict.items(), key=lambda x:(x[0]))\n",
    "        result = 0\n",
    "        pre_sum = 1\n",
    "        for i in range(1, len(num_times)):\n",
    "            result += num_times[i][1] * i\n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
